home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-04
/
ddj0492.zip
/
REDBLACK.ASC
< prev
next >
Wrap
Text File
|
1992-03-10
|
2KB
|
90 lines
_RED-BLACK TRESS_
by Bruce Schneier
[Example 1: Insert operation, in pseudocode]
RedBlackInsert(T,x)
{
TreeInsert(T,x)
color(x) <-- Red
while x != root(T) and color(p(x))==Red
if p(x)==left(p(p(x)))
y <-- right(p(p(x)))
if color(y)==Red
color(p(x)) <-- Black
color(y) <-- Black
color(p(p(x))) <-- Red
x <-- p(p(x))
else
if x==right(p(x))
x <-- p(x)
RotateLeft(T,x)
color(p(x)) <-- Black
color(p(p(x))) <-- Red
RotateRight(T, p(p(x)))
else
/* this is the same as the "then" clause,
* with "right" and "left" interchanged */
color(root(T)) <-- Black
}
[Example 2: Delete operation, in pseudocode]
RedBlackDelete(T,z)
{
if left(z)==nil(T) or right(z)==nil(T)
y <-- z
else
y <-- TreeSuccessor(z)
if left(y) != nil(T)
x <-- left(y)
else
x <-- right(y)
p(x) <-- p(y)
if p(y) == nil(T)
root(T) <-- x
else
if y==left(p(y))
left(p(x)) <-- x
else
right(p(y)) <-- x
if y != z
key(z) <-- key(y)
/* if y has other fields, copy them too */
if color(y)==Black
then RBDeleteFixup(T,x)
}
RBDeleteFixup(T,x)
{
while x != root(T) and color(x)==Black
if x==left(p(x))
w <-- right(p(x))
if color(w) <-- Black
color(p(x)) <-- Red
RotateLeft(T,p(x))
w <-- right(p(x))
if color(left(w)) == Black and color(right(w))==Black
color(w) <-- Red
x <-- parent(x)
else
if color(right(w)) == Black
color(left(w)) <-- Black
color(w) <-- Red
RotateRight(T,w)
w <-- right(p(x))
color(w) <-- color(p(x))
color(p(x)) <-- Black
color(right(w)) <-- Black
RotateLeft(T,p(x))
x <-- root(T)
else
/* this is same as "then" clause,
* except that right and left are exchanged */
color(x) <--Black
}